'''
Created on May 10, 2011

@author: Santi
'''
from _base import Game

class Board(object):
    def __init__(self, state_map, current_player, current_turn=0):
        ''' state_map es un mapa que representa el tablero: Tiene como
            clave una posicion y como valor la pieza que ocupa dicha posicion.
            Todas las posiciones que no sean claves de state_map debe considerarse
            vacias. Esta estructura nos da un mejor aprovechamiento de memoria
            que una matriz (lista de listas).
        '''
        self.pieces = state_map
        self.current_player = current_player
        self.current_turn = current_turn
        
    def copy(self):
        return Board(self.pieces.copy(), self.current_player, self.current_turn)

class Move(object):
    def __init__(self, from_position, to_position):
        self.from_position = from_position
        self.to_position = to_position
        
    def __eq__(self, other):
        if isinstance(other, Move):
            return self.__repr__() == other.__repr__()
        return
    
    def __str__(self):
        return str(self.from_position[0])+str(self.from_position[1])+"-"+str(self.to_position[0])+str(self.to_position[1])
    
    def __repr__(self):
        return str(self.from_position[0])+str(self.from_position[1])+"-"+str(self.to_position[0])+str(self.to_position[1])

class Tablut(Game):
    (WHITE_PLAYER, BLACK_PLAYER) = ('Blancas', 'Negras')
    (WHITE_COUNTER, BLACK_COUNTER, WHITE_KING) = (0, 1, 2)
    (ESCAPE_SQUARE, THRONE_SQUARE, REGULAR_SQUARE) = (3, 4, 5)
    MAX_TURNS = 500
    
    special_positions = {
        (0, 0): ESCAPE_SQUARE,
        (0, 8): ESCAPE_SQUARE,
        (8, 0): ESCAPE_SQUARE,
        (8, 8): ESCAPE_SQUARE,
        (4, 4): THRONE_SQUARE
    }
    PLAYERS = (WHITE_PLAYER, BLACK_PLAYER)
    
    def __init__(self, board=None):
        Game.__init__(self, *Tablut.PLAYERS)
        if board:
            self.state = board
        else:
            self.state = Board(INITIAL_STATE.copy(), Tablut.WHITE_PLAYER)
    
    def _game_finished(self):
        king_pos = [key for key in self.state.pieces.keys() if self.state.pieces[key] == Tablut.WHITE_KING][0]
        return self._black_wins(king_pos) or self._white_wins(king_pos)
    
    def moves(self):
        if self._game_finished() or self.state.current_turn >= Tablut.MAX_TURNS:
            return {}
        moves = []
        for position, piece in self.state.pieces.items():
            if self.belongs_to(piece, self.state.current_player):
                # derecha
                for i in xrange(position[1]+1, 9):
                    new_pos = (position[0], i)
                    # la colision detiene el bucle
                    if new_pos in self.state.pieces.keys():
                        break
                    if self.move_is_valid(position, new_pos):
                        moves.append(Move(position, new_pos))
                # izquierda
                for i in xrange(position[1]-1, -1, -1):
                    new_pos = (position[0], i)
                    # la colision detiene el bucle
                    if new_pos in self.state.pieces.keys():
                        break
                    if self.move_is_valid(position, new_pos):
                        moves.append(Move(position, new_pos))
                # arriba
                for i in xrange(position[0]-1, -1, -1):
                    new_pos = (i, position[1])
                    # la colision detiene el bucle
                    if new_pos in self.state.pieces.keys():
                        break
                    if self.move_is_valid(position, new_pos):
                        moves.append(Move(position, new_pos))
                # abajo
                for i in xrange(position[0]+1, 9):
                    new_pos = (i, position[1])
                    # la colision detiene el bucle
                    if new_pos in self.state.pieces.keys():
                        break
                    if self.move_is_valid(position, new_pos):
                        moves.append(Move(position, new_pos))
        if self.state.current_player == Tablut.WHITE_PLAYER:
            if moves:
                return { Tablut.WHITE_PLAYER: moves}
            else:
                return {}
        else:
            if moves:
                return { Tablut.BLACK_PLAYER: moves}
            else:
                return {}
    
    def move_is_valid(self, position, new_pos):
        return (
            (
                # no soy el rey
                self.state.pieces[position] != Tablut.WHITE_KING and
                # no puedo pararme en las esquinas ni el trono
                new_pos not in self.special_positions.keys()
            ) or (
                # soy el rey
                self.state.pieces[position] == Tablut.WHITE_KING and
                # no puedo volver al trono
                new_pos != (4, 4)
            ) and (
                # evito moverme hacia la misma posicion
                position != new_pos
            )
        )
    
    def belongs_to(self, piece, player):
        ''' Retorna true si y solo si la pieza piece corresponde al jugador player.
        '''
        if player == Tablut.WHITE_PLAYER:
            return piece == Tablut.WHITE_COUNTER or piece == Tablut.WHITE_KING
        else:
            return piece == Tablut.BLACK_COUNTER
    
    def results(self):
        king_pos = [key for key in self.state.pieces.keys() if self.state.pieces[key] == Tablut.WHITE_KING][0]
        INFINITY = 0x7FFFFFFF
        if self._black_wins(king_pos):
            return { Tablut.BLACK_PLAYER: INFINITY, Tablut.WHITE_PLAYER: -INFINITY }
        elif self._white_wins(king_pos):
            return { Tablut.BLACK_PLAYER: -INFINITY, Tablut.WHITE_PLAYER: INFINITY }
        elif self._draw():
            return { Tablut.BLACK_PLAYER: 0, Tablut.WHITE_PLAYER: 0 }
        else:
            return None
            
    def _white_wins(self, king_pos):
        ''' Las blancas ganan unicamente cuando el rey alcanza una de las esquinas.
        '''
        black_counters = [value for value in self.state.pieces.values() if value == Tablut.BLACK_COUNTER]
        # si no tengo al menos tres negras no puedo capturar al rey
        enough_black_counters = len(black_counters) >= 3
        corners = [(0, 0), (0, 8), (8, 0), (8, 8)]
        return king_pos in corners or not enough_black_counters
    
    def _black_wins(self, king_pos):
        ''' Las negras ganan cuando el rey esta rodeado por cuatro piezas enemigas,
            o tres piezas enemigas y el trono.
        '''
        # si tengo tres negras alrededor
        if len(self.surrounding_black_counters(king_pos)) == 3:
            throne_pos = (4, 4)
            # chequeo para ver si no estoy al lado del trono
            if (king_pos[0], king_pos[1]+1) == throne_pos or (king_pos[0], king_pos[1]-1) == throne_pos or (king_pos[0]+1, king_pos[1]) == throne_pos or (king_pos[0]-1, king_pos[1]) == throne_pos:
                # Si tengo tres negras alrededor mas el trono, ganan las negras
                return True
            # chequeo si no estoy en un lateral
            else:
                surrounding_positions = self._surrounding_positions(king_pos)
                for pos in surrounding_positions:
                    if self._out_of_bounds(pos):
                        return True
                
        if len(self.surrounding_black_counters(king_pos)) == 4:
            return True
        # en todo otro caso, las negras no han ganado
        return False
    
    def _surrounding_positions(self, pos):
        return [
            (pos[0], pos[1]+1),
            (pos[0], pos[1]-1),
            (pos[0]+1, pos[1]),
            (pos[0]-1, pos[1])
        ]
    
    def _out_of_bounds(self, pos):
        if pos[0] > 8 or pos[0] < 0:
            return True
        if pos[1] > 8 or pos[1] < 0:
            return True
    
    def _draw(self):
        ''' Para cualquier estado del juego en el que el jugador del turno que sigue no tenga movimientos y
            ninguno sea el ganador, se dan tablas (empate). Llamar _draw despues de _white_wins y _black_wins
            porque no se chequean esas dos precondiciones.
        '''
        moves = self.moves()
        if not moves:
            return True
        elif self.state.current_turn == Tablut.MAX_TURNS:
            return True
        else:
            return False
    
    def surrounding_black_counters(self, pos, other_state=None):
        if other_state != None:
            state = other_state
        else:
            state = self.state
        return [(i, pos[1])
                for i in [pos[0]+1, pos[0]-1]
                if state.pieces.get((i, pos[1]), None) == Tablut.BLACK_COUNTER and
                   (1 <= i <= 8)
               ] + [(pos[0], j)
                    for j in [pos[1]+1, pos[1]-1]
                    if state.pieces.get((pos[0], j), None) == Tablut.BLACK_COUNTER and
                       (1 <= j <= 8)]
    
    def surrounding_white_counters(self, pos, other_state=None):
        if other_state != None:
            state = other_state
        else:
            state = self.state
        return [(i, pos[1])
                for i in [pos[0]+1, pos[0]-1]
                if state.pieces.get((i, pos[1]), None) == Tablut.WHITE_COUNTER and
                   (1 <= i <= 8)
               ] + [(pos[0], j)
                    for j in [pos[1]+1, pos[1]-1]
                    if state.pieces.get((pos[0], j), None) == Tablut.WHITE_COUNTER and
                       (1 <= j <= 8)]
    
    def next(self, **moves):
        move = moves[self.state.current_player]
        new_state = self.state.copy()
        new_state.current_turn+=1
        moving_piece = new_state.pieces.pop(move.from_position)
        new_state.pieces[move.to_position] = moving_piece
        if moving_piece != Tablut.WHITE_KING:
            if self.state.current_player == Tablut.WHITE_PLAYER:
                surrounding_enemies = self.surrounding_black_counters(move.to_position, new_state)
                ally_type = Tablut.WHITE_COUNTER
            else:
                surrounding_enemies = self.surrounding_white_counters(move.to_position, new_state)
                ally_type = Tablut.BLACK_COUNTER
            relative_positions = {
                (move.to_position[0], move.to_position[1]+1): "right",
                (move.to_position[0], move.to_position[1]-1): "left",
                (move.to_position[0]+1, move.to_position[1]): "down",
                (move.to_position[0]-1, move.to_position[1]): "up"
            }
            for enemy_pos in surrounding_enemies:
                # capture la pieza de la derecha?
                if relative_positions[enemy_pos] == "right" and self._is_ally_or_dark_square((move.to_position[0], move.to_position[1]+2), ally_type):
                        # capturada!
                        new_state.pieces.pop(enemy_pos)
                elif relative_positions[enemy_pos] == "left" and self._is_ally_or_dark_square((move.to_position[0], move.to_position[1]-2), ally_type):
                    new_state.pieces.pop(enemy_pos)
                elif relative_positions[enemy_pos] == "down" and self._is_ally_or_dark_square((move.to_position[0]+2, move.to_position[1]), ally_type):
                    new_state.pieces.pop(enemy_pos)
                elif relative_positions[enemy_pos] == "up" and self._is_ally_or_dark_square((move.to_position[0]-2, move.to_position[1]), ally_type):
                    new_state.pieces.pop(enemy_pos)
        # cambio de jugador
        if self.state.current_player == Tablut.WHITE_PLAYER:
            new_state.current_player = Tablut.BLACK_PLAYER
        else:
            new_state.current_player = Tablut.WHITE_PLAYER
        return Tablut(new_state)
    
    def _is_ally_or_dark_square(self, pos, ally_type):
        # Es una esquina?
        if pos in [(0, 0), (0, 8), (8, 0), (8, 8)]:
            return True
        return self.state.pieces.get(pos, None) == ally_type

    def __str__(self):
        return str(self.state.pieces) + " - " + str(self.state.current_player)
    
    def __repr__(self):
        return str(self.state.pieces) + " - " + str(self.state.current_player)

INITIAL_STATE = {
    (4, 4): Tablut.WHITE_KING,
    # piezas blancas
    # arriba
    (2, 4): Tablut.WHITE_COUNTER,
    (3, 4): Tablut.WHITE_COUNTER,
    # derecha
    (4, 6): Tablut.WHITE_COUNTER,
    (4, 5): Tablut.WHITE_COUNTER,
    # abajo
    (5, 4): Tablut.WHITE_COUNTER,
    (6, 4): Tablut.WHITE_COUNTER,
    # izquierda
    (4, 2): Tablut.WHITE_COUNTER,
    (4, 3): Tablut.WHITE_COUNTER,

    # piezas negras
    # arriba
    (0, 3): Tablut.BLACK_COUNTER,
    (0, 4): Tablut.BLACK_COUNTER,
    (0, 5): Tablut.BLACK_COUNTER,
    (1, 4): Tablut.BLACK_COUNTER,
    # derecha
    (3, 8): Tablut.BLACK_COUNTER,
    (4, 8): Tablut.BLACK_COUNTER,
    (5, 8): Tablut.BLACK_COUNTER,
    (4, 7): Tablut.BLACK_COUNTER,
    # izquierda
    (3, 0): Tablut.BLACK_COUNTER,
    (4, 0): Tablut.BLACK_COUNTER,
    (5, 0): Tablut.BLACK_COUNTER,
    (4, 1): Tablut.BLACK_COUNTER,
    # abajo
    (8, 3): Tablut.BLACK_COUNTER,
    (8, 4): Tablut.BLACK_COUNTER,
    (8, 5): Tablut.BLACK_COUNTER,
    (7, 4): Tablut.BLACK_COUNTER
}